class Solution {
public:
    string generateSpaces(int num) {
      string ret;
      for (int i = 0; i < num; ++i) {
        ret += " ";
      }
      return ret;
    }

    vector<string> fullJustify(vector<string> &words, int L) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
      int n = words.size();
      vector<string> ans;

      for (int i = 0; i < n; ) {
        int j = i + 1;
        int totalLength = words[i].length();
        int wordLength = words[i].length();

        while (j < n && totalLength + words[j].length() + 1 <= L) {
          totalLength += words[j].length() + 1;
          wordLength += words[j].length();
          ++j;
        }

        string line = words[i];
        if (j >= n) { // the last line
          for (int k = i + 1; k < n; ++k) {
            line += " ";
            line += words[k];
          }
          line += generateSpaces(L - totalLength);
        } else {
          int l = L - wordLength;
          for (int k = i + 1; k < j; ++k) {
            if (l % (j - k) == 0) {
              line += generateSpaces(l / (j - k));
              l -= l / (j - k);
            } else {
              line += generateSpaces(l / (j - k) + 1);
              l -= l / (j - k) + 1;
            }
            line += words[k];
          }
          line += generateSpaces(l);
        }
        ans.push_back(line);
        i = j;
      }
      return ans;
    }
};
